/*
 * File: maze.c
 * ------------
 * This program solves a maze by recursive backtracking.
 */

#include <stdio.h>
#include "genlib.h"
#include "graphics.h"
#include "mazelib.h"
#include "simpio.h"

/*
 * Constants
 * ---------
 * MazeFile -- Name of the file containing the maze
 */

//#define MazeFile "pathlen.maz"
#define NoSolution 10000

/* Private function prototypes */

static bool SolveMaze(pointT pt);
static pointT AdjacentPoint(pointT pt, directionT dir);
int ShortestPathLength(pointT pt);

/* Main program */

main() {
	string mazefile = "";

	printf("Input mazefile: \n");
	mazefile = GetLine();
    InitGraphics();
	SetPauseTime(0.01);
    ReadMazeMap(mazefile);
	printf("%d\n", ShortestPathLength(GetStartPosition()));
}

int ShortestPathLength(pointT pt) {
	directionT dir;
	int min = NoSolution, steps = 0;

	if (OutsideMaze(pt)) return 0;
	if (IsMarked(pt)) return NoSolution;
	MarkSquare(pt);
	
	for (dir = North; dir <= West; dir++) {
        if (!WallExists(pt, dir)) {
            steps = ShortestPathLength(AdjacentPoint(pt, dir));
			if (steps < min) min = steps;
        }
    }
	UnmarkSquare(pt);
	if (min < NoSolution) return min+1;
    return NoSolution;	
}

/*
 * Function: AdjacentPoint
 * Usage: newpt = AdjacentPoint(pt, dir);
 * --------------------------------------
 * This function returns the pointT that results from moving
 * one square from pt in the direction specified by dir.  For
 * example, if pt is the point (1,1), AdjacentPoint(pt, East)
 * would return the point (2,1).
 */

static pointT AdjacentPoint(pointT pt, directionT dir)
{
    pointT newpt;

    newpt = pt;
    switch (dir) {
      case North: newpt.y++; break;
      case East:  newpt.x++; break;
      case South: newpt.y--; break;
      case West:  newpt.x--; break;;
    }
    return (newpt);
}
